package com.gao.alg.geek;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 前，中，后序遍历。（根据访问根节点的先后进行区分）
 * 层序遍历
 */
public class BinaryTree {

    // 使用递归方式
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal1(TreeNode root) {
        if (root == null){
            return null;
        }
        list.add(root.val);
        preorderTraversal1(root.left);
        preorderTraversal1(root.right);
        return list;
    }
    public void midOrderTraversal(TreeNode root) {
        if (root == null){
            return ;
        }
        midOrderTraversal(root.left);
        System.out.println(root.val);
        midOrderTraversal(root.right);
    }
    public void backOrderTraversal(TreeNode root) {
        if (root == null){
            return ;
        }
        backOrderTraversal(root.left);
        backOrderTraversal(root.right);
        System.out.println(root.val);
    }

    // 使用迭代方式

    public void preorderTraversal2(TreeNode root) {
        if (root == null){
            return;
        }
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
    }


    public List<Integer> midOrderTraversal2(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null){
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            list.add(node.val);
            if (node.right !=null){
                cur = node.right;
            }
        }
        return list;
    }

    public void backOrderTraversal2(TreeNode root) {
        if (root == null){
            return ;
        }

    }
}
